#ifndef __BITREE_H
#define __BITREE_H

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <cassert>
#include <cstdlib>
using namespace std;

template <typename T, typename K>
class _bithrtree
{
public:
	K key;
    T *lchild;
    T *rchild;
	T *parent;
	int ltag;
	int rtag;
	_bithrtree()
	{
		lchild = rchild = NULL;
		ltag = rtag = 0;
	}
};

template <typename T>
void bithrtree_init(T *&rt)
{
    rt = NULL;
}

template <typename K>
static void input_bithrtree(const char *filename, vector<K> &pre, vector<K> &in)
{
	int n;
	ifstream input;

    input.open(filename);
    if (!input){
        cerr << "'" << filename << "' can not be opened." << endl;
        exit(-1);
    }
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        pre.push_back(t);
    }
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        in.push_back(t);
    }

	input.close();
}

template <typename T, typename K>
static T* _bithrtree_create(vector<K> &pre, int pl, int ph, vector<K> &in, int il, int ih, T *pa)
{
    T *rt;
    int i;

    assert(ph-pl == ih-il);
    if (ph < pl) return NULL;
    for (i = il; i <= ih; i++)
        if (in[i] == pre[pl]) break;
    assert(i <= ih);
    rt = new T;
    assert(rt);
    rt->key = pre[pl];
	rt->parent = pa;
    rt->lchild = _bithrtree_create<T,K>(pre, pl+1, pl+i-il, in, il, i-1, rt);
    rt->rchild = _bithrtree_create<T,K>(pre, pl+i-il+1, ph, in, i+1, ih, rt);

    return rt;
}

/***********************************************************
						preorder
***********************************************************/

template <typename T>
static void bithrtree_preorder_threading(T *&rt)
{
	stack<T*> s;
	T *prev = NULL, *p;

	p = rt;
	while (p || !s.empty()){
		if (p){
			if (!p->lchild){
				p->ltag = 1;
				p->lchild = prev;
			}
			if (prev && !prev->rchild){
				prev->rtag = 1;
				prev->rchild = p;
			}
			s.push(p);

			prev = p;
			if (!p->ltag)
				p = p->lchild;
			else
				p = NULL;
		}
		else{
			p = s.top(); s.pop();
			if (!p->rtag)
				p = p->rchild;
			else
				p = NULL;
		}
	}
	if (prev && !prev->rchild)		// prev is NULL while rt is NULL
		prev->rtag = 1;				// p must be prev's right child and NULL
}

template <typename T, typename K>
void bithrtree_preorder_create(T *&rt, const char* filename)
{
    vector<K> pre, in;
	T *prev = NULL;

	input_bithrtree(filename, pre, in);
    assert(pre.size() == in.size());
    rt = _bithrtree_create<T,K>(pre, 0, pre.size()-1, in, 0, in.size()-1, NULL);
	bithrtree_preorder_threading(rt);
}

template <typename T>
void bithrtree_destory(T *&rt)
{
	if (!rt)
		return;
	
	if (!rt->ltag)
		bithrtree_destory(rt->lchild);
	if (!rt->rtag)
		bithrtree_destory(rt->rchild);
	delete rt;
	rt = NULL;
}

template <typename T>
T *bithrtree_preorder_first(T *rt)
{
	return rt;
}

template <typename T>
T *bithrtree_preorder_last(T *rt)
{
	T *p = rt;
	while (p && !p->rtag)
		p = p->rchild;
	return p;
}

template <typename T>
T *bithrtree_preorder_next(T *cur)
{
	if (!cur)
		return NULL;

	if (cur->rtag)			// the right child is thread
		return cur->rchild;
	else if (!cur->ltag)	// the left child exists
		return cur->lchild;
	else
		return cur->rchild;	// the left child does not exist 
							// while the right child does.
}

template <typename T>
T *bithrtree_preorder_prev(T *cur)
{
	if (!cur)
		return NULL;

	if (cur->ltag)			// the left child is thread
		return cur->lchild;
	else if (!cur->parent ||				// root 
			 cur == cur->parent->lchild ||	// the left child of parent
			 cur->parent->ltag				// the right child of parent 
											// and the left child of parent does not exist
			 )
		return cur->parent;
	else									// the right child of parent
											// and the last node of the left subtree
		return bithrtree_preorder_last(cur->parent->lchild);
}

/***********************************************************
						inorder
***********************************************************/

template <typename T>
static void bithrtree_inorder_threading(T *&rt)
{
	stack<T*> s;
	T *prev = NULL, *p;

	p = rt;
	while (p || !s.empty()){
		if (p){
			s.push(p);
			if (!p->ltag)
				p = p->lchild;
			else
				p = NULL;
		}
		else{
			p = s.top(); s.pop();

			if (!p->lchild){
				p->ltag = 1;
				p->lchild = prev;
			}
			if (prev && !prev->rchild){
				prev->rtag = 1;
				prev->rchild = p;
			}
			prev = p;

			if (!p->rtag)		// for inorder, the rchild of a node 
								// popped from the stack must not be
								// threaded. So, this branch is not
								// necessary.
				p = p->rchild;
			else
				p = NULL;
		}
	}
	if (prev && !prev->rchild)	// prev is NULL whild rt is NULL
		prev->rtag = 1;			// p must be prev's right child and NULL
}

template <typename T, typename K>
void bithrtree_inorder_create(T *&rt, const char* filename)
{
    vector<K> pre, in;
	T *prev = NULL;

	input_bithrtree(filename, pre, in);
    assert(pre.size() == in.size());
    rt = _bithrtree_create<T,K>(pre, 0, pre.size()-1, in, 0, in.size()-1, NULL);
	bithrtree_inorder_threading(rt);
}

template <typename T>
T *bithrtree_inorder_first(T *rt)
{
	T *p = rt;
	while (p && !p->ltag)
		p = p->lchild;
	return p;
}

template <typename T>
T* bithrtree_inorder_last(T *rt)
{
	T *p = rt;
	while (p && !p->rtag)
		p = p->rchild;
	return p;
}

template <typename T>
T *bithrtree_inorder_next(T *cur)
{
	if (!cur)
		return NULL;

	if (cur->rtag)				// right child is thread
		return cur->rchild;
	else						// right child exists
		return bithrtree_inorder_first(cur->rchild);
}

template <typename T>
T *bithrtree_inorder_prev(T *cur)
{
	if (!cur)
		return NULL;

	if (cur->ltag)				// left child is thread
		return cur->lchild;
	else						// left child exists
		return bithrtree_inorder_last(cur->lchild);
}

/***********************************************************
						postorder
***********************************************************/
template <typename T>
struct snode{
	T *rt;
	int tag;
};

template <typename T>
static void bithrtree_postorder_threading(T *&rt)
{
	snode<T> n;
	stack< snode<T> > s;
	T *prev, *p;

	p = rt; prev = NULL;
	while (p || !s.empty()){
		if (p){
			n.rt = p; n.tag = 0;
			s.push(n);
			p = p->lchild;
		}
		else{
			n = s.top(); s.pop();
			p = n.rt;
			if (!n.tag){
				n.tag = 1; s.push(n);
				p = p->rchild;
			}
			else{
				if (!p->lchild){
					p->ltag = 1;
					p->lchild = prev;
				}
				if (prev && !prev->rchild){
					prev->rtag = 1;
					prev->rchild = p;
				}
				prev = p;
				p = NULL;
			}
		}
	}
	if (prev && !prev->rchild)
		prev->rtag = 1;
}

template <typename T, typename K>
void bithrtree_postorder_create(T *&rt, const char* filename)
{
    vector<K> pre, in;
	T *prev = NULL;

	input_bithrtree(filename, pre, in);
    assert(pre.size() == in.size());
    rt = _bithrtree_create<T,K>(pre, 0, pre.size()-1, in, 0, in.size()-1, NULL);
	bithrtree_postorder_threading(rt);
}

template <typename T>
T *bithrtree_postorder_first(T *rt)
{
	T *p = rt;
	do{
		while (p && !p->ltag)
			p = p->lchild;
		if (p && !p->rtag)
			p = p->rchild;
	}while (p && !p->rtag);

	return p;
}

template <typename T>
T *bithrtree_postorder_last(T *rt)
{
	return rt;
}

template <typename T>
T *bithrtree_postorder_next(T *cur)
{
	if (!cur)
		return NULL;

	if (cur->rtag)
		return cur->rchild;
	else if (!cur->parent ||				// cur is root, return NULL
			 cur == cur->parent->rchild ||	// cur is its parent's right child
			 cur->parent->rtag				// cur is its parent's left child
											// and its parent has not right child
			)
		return cur->parent;					// cur is its parent's left and the parent
											// has right child
	else
		return bithrtree_postorder_first(cur->parent->rchild);
}

template <typename T>
T *bithrtree_postorder_prev(T *cur)
{
	if (!cur)
		return NULL;

	if (cur->ltag)
		return cur->lchild;
	else if (!cur->rtag)
		return cur->rchild;
	else
		return cur->lchild;
}

#endif
